In this paper, a puzzle called Cell-Maze is analyzed. In this puzzle, cells are arranged in checker board squares. Each cell is rotated when a player arrives at the cell. Cell-Maze asks whether or not a player started from a start cell can reach a goal cell. The reachability problem for ordinary graphs can be easily solved in linear time, however a reachability problem for the network such as Cell-Maze may be extremely difficult. In this paper, NP-hardness of this puzzle is proved. It is proved by reducing Hamiltonian Circuit Problem of directed planar graph G such that each vertex involved in just three arcs. Furthermore, we consider subproblems, which can be solved in polynomial time.

This paper develops a prediction model for evaluating the influence of propagation attenuation due to aircraft's flying across the earth-satellite link. This prediction model is based on the Aperture-field method of Huygens-Fresnel wave theory. Considering arriving and taking off course around airport, attenuation impairment is calculated for different types of aircrafts and flight directions. In order to verify this model's accuracy, numerical results are compared with measurement values. The calculations agree well with the measurements. Ground antenna directivity and anticipated impairment to digital broadcasting system such as Perfect TV are also discussed.

A detabase system that provides step-by-step guidance for LSI failure analysts has been developed. This system has three main functions: database, navigator, and chip tracking. The datebase stores failure analysis information such as analysis method and failure mechanisms including image data. It also stores conditions and results of each analysis step and decisions to proceeds to the next analysis step. With 2000 failure analysis cases, data retrieval takes 6.6 seconds, a table containing 20 photos is presented in 6.5 seconds, and a different set of data can be displayed in 0.6 seconds. The navigator displays a standard analysis procedure illustrated in flow charts.The chip tracking shows where the particular chip is and what analysis it is undergoing, which is useful for the situation where many chips are simultaneously analyzed. Thus, this system has good enough functions of analysis procedure management and performance of quick data access to make failure analysis easier and more successful.

Layer-by-layer sequential adsorption process of polyelectrolytes had conventionally been used for the fabrication of the ultra-thin organic film formed by various polymers with different polarity of charge. In this study, hydrophobic Ruthenium complex monomer (tris (bilyridyl) ruthenium (II) hexafluorophosphate) was micelle-wrapped with an anionic surfactant, sodium dodecylbenzenesulfonate, and was assembled with PAH (poly (allylamine hydrochloride)) which has the opposite charge on ITO substrates. With this method, we succeed in fabricating ultra-thin organic films even when the adsorption material is not polymer but monomer. Moreover it was found that the bilayer thickness of the self-assembled (Ru micelle/PAH) was systematically changed by adjusting the solution pH of each bath. By using this process, EL device was fabricated by depositing the thin film of micelle-wrapping ruthenium complex monomer on ITO and formed Bi electrode on top of the film. Light emission was observed by applying voltage to this device.

When using a wireless capsule endoscope (WCE), it is important to know WCE location. In this paper, we focus on a time of arrival (TOA)-based localization technique, as it has better location estimation performance than other radio frequency-based techniques. However, the propagation speed of signals transmitted from inside of a human body varies depending on which biological tissues they pass through. For this reason, almost all of conventional TOA-based methods have to obtain the relative permittivity of the passed biological tissues or the propagation speed beforehand through another measurement system, i.e., magnetic resonance imaging (MRI) or computational tomography (CT). To avoid such troublesome pre-measurement, we propose a hybrid TOA/received signal strength indicator (RSSI)-based method, which can simultaneously estimate the WCE location and the averaged relative permittivity of the human body. First, we derive the principle of RSSI-based relative permittivity estimation from an finite difference time domain (FDTD) simulation. Second, we combine the TOA-based localization and the proposed RSSI-based relative permittivity estimation, and add them to the particle filter tracking technique. Finally, we perform computer simulations to evaluate the estimation accuracy of the proposed method. The simulation results show that the proposed method can accomplish good localization performance, 1.3mm, without pre-measurement of the human body structure information.

Suppose that we are given two vertex covers C0 and Ct of a graph G, together with an integer threshold k ≥ max{|C0|, |Ct|}. Then, the vertex cover reconfiguration problem is to determine whether there exists a sequence of vertex covers of G which transforms C0 into Ct such that each vertex cover in the sequence is of cardinality at most k and is obtained from the previous one by either adding or deleting exactly one vertex. This problem is PSPACE-complete even for planar graphs. In this paper, we first give a linear-time algorithm to solve the problem for even-hole-free graphs, which include several well-known graphs, such as trees, interval graphs and chordal graphs. We then give an upper bound on k for which any pair of vertex covers in a graph G has a desired sequence. Our upper bound is best possible in some sense.

For a given graph G=(V, E), edge capacities c(e) for edges e E, and flow-demands d(v) for nodes v V, a problem of finding the minimum size source-set S V such that the maximum flow-amount between S and v is greater than or equal to d(v) for every v V is called generalized plural cover problem (GPC). For this problem, O(np s(n,m)) time algorithm is presented, where n, m, and p is the number of nodes, edges, and different values of d(v), respectively, and s(n,m) is the time required to solve the maximum flow problem of a graph with n nodes and m edges. This algorithm also constructs a set of optimal solutions in the same time. This property is convenient for applying it to real problems, because other constraints can also be taken into account.

This paper describes the structure and properties of superconductive small antennas with thin-film matching circuits. These circuits make it possible to realize small antennas, 38 mm20 mm16 mm in size. This is one quarter the length of our previously reported ceramic antennas. The actual gain of this antennas was -4.5 dBi at 470 MHz. This value is 5.5 dB higher than that of Cu antennas with exactly the same structure.

Let m 2, n 2, and q 2 be positive integers. Let Sr and Sb be two disjoint sets of points in the plane such that no three points of Sr Sb are collinear, |Sr| = nq, and |Sb| = mq. This paper shows that Kaneko and Kano's conjecture is true, i.e., there are q disjoint convex regions of the plain such that each region includes n points of Sr and m points of Sb. This is a generalization of 2-dimension Ham Sandwich Theorem.

We study the problem of transforming one (vertex) c-coloring of a graph into another one by changing only one vertex color assignment at a time, while at all times maintaining a c-coloring, where c denotes the number of colors. This decision problem is known to be PSPACE-complete even for bipartite graphs and any fixed constant c ≥ 4. In this paper, we study the problem from the viewpoint of graph classes. We first show that the problem remains PSPACE-complete for chordal graphs even if c is a fixed constant. We then demonstrate that, even when c is a part of input, the problem is solvable in polynomial time for several graph classes, such as k-trees with any integer k ≥ 1, split graphs, and trivially perfect graphs.

As TCP/IP networks develop, various type of applications or services are appearing. Especially, many people want to use real time multicast applications over TCP/IP networks like a TV conference system. Most of the current TCP/IP networks, however, still do not support QoS guarantees using RSVP, so that they provide only a best-effort service. Therefore, such real time applications must control data transmitting rate by the network or receiver's condition. However, it is difficult to control data rate over a multicast session, since every receiver on a multicast network does not necessarily have the same environment. To solve this problem, the authors proposed a locally adaptive control intermediate system. This paper describes a rate-adaptive real-time multicast system with locally adaptive packet flow control.

The challenges posed by big data in the 21st Century are complex: Under the previous common sense, we considered that polynomial-time algorithms are practical; however, when we handle big data, even a linear-time algorithm may be too slow. Thus, sublinear- and constant-time algorithms are required. The academic research project, “Foundations of Innovative Algorithms for Big Data,” which was started in 2014 and will finish in September 2021, aimed at developing various techniques and frameworks to design algorithms for big data. In this project, we introduce a “Sublinear Computation Paradigm.” Toward this purpose, we first provide a survey of constant-time algorithms, which are the most investigated framework of this area, and then present our recent results on sublinear progressive algorithms. A sublinear progressive algorithm first outputs a temporary approximate solution in constant time, and then suggests better solutions gradually in sublinear-time, finally finds the exact solution. We present Sublinear Progressive Algorithm Theory (SPA Theory, for short), which enables to make a sublinear progressive algorithm for any property if it has a constant-time algorithm and an exact algorithm (an exponential-time one is allowed) without losing any computation time in the big-O sense.

A novel nonlinear directional coupler consisting of tapered and uniform waveguides with self-focusing or self-defocusing nonlinear material is proposed to improve all-optical switching characteristics. Its switching characteristics are analyzed by using a beam propagation method based on the Galerkin's finite element technique (FE-BPM), in which nonuniform sampling spacings along the transverse coordinate are adopted. It is presented that the tapered nonlinear directional coupler shows fairly distinct 'high' and 'low' states of output power with steep transition versus input power. This property is discussed in comparison with conventional nonlinear directional couplers consisting of uniform symmetric and uniform asymmetric coupled waveguides. In addition, the effects of loss on the characteristics of tapered nonlinear directional coupler are examined.

The composed thermo-e.m.f. caused by a suitable connection, which is called C-connection, becomes lower than the thermo-e.m.f. of individual reed switch. The composed thermo-e.m.f. is discussed by Nernst effect on the reed contact and is given a reasonable explication by this effect.

Suppose that each arc in a digraph D = (V,A) has two costs of non-negative integers, called a spine cost and a leaf cost. A caterpillar is a directed tree consisting of a single directed path (of spine arcs) and leaf vertices each of which is incident to the directed path by exactly one incoming arc (leaf arc). For a given terminal set K ⊆ V, we study the problem of finding a caterpillar in D such that it contains all terminals in K and its total cost is minimized, where the cost of each arc in the caterpillar depends on whether it is used as a spine arc or a leaf arc. In this paper, we first show that the problem is NP-hard for any fixed constant number of terminals with |K| ≥ 3, while it is solvable in polynomial time for at most two terminals. We also give an inapproximability result for any fixed constant number of terminals with |K| ≥ 3. Finally, we give a linear-time algorithm to solve the problem for digraphs with bounded treewidth, where the treewidth for a digraph D is defined as the one for the underlying graph of D. Our algorithm runs in linear time even if |K| = O(|V|), and the hidden constant factor of the running time is just a single exponential of the treewidth.

Tracking capsule endoscope location is one of the promising applications offered by implant body area networks (BANs). When tracking the capsule endoscope location, i.e., continuously localize it, it is effective to take the weighted sum of its past locations to its present location, in other words, to low-pass filter its past locations. Furthermore, creating an exact mathematical model of location transition will improve tracking performance. Therefore, in this paper, we investigate two tracking methods with received signal strength indicator (RSSI)-based localization in order to solve the capsule endoscope location tracking problem. One of the two tracking methods is finite impulse response (FIR) filter-based tracking, which tracks the capsule endoscope location by averaging its past locations. The other one is particle filter-based tracking in order to deal with a nonlinear transition model on the capsule endoscope. However, the particle filter requires that the particle weight is calculated according to its condition (namely, its likelihood value), while the transition model on capsule endoscope location has some model parameters which cannot be estimated from the received wireless signal. Therefore, for the purpose of applying the particle filter to capsule endoscope tracking, this paper makes some modifications in the resampling step of the particle filter algorithm. Our computer simulation results demonstrate that the two tracking methods can improve the performance as compared with the conventional maximum likelihood (ML) localization. Furthermore, we confirm that the particle filter-based tracking outperforms the conventional FIR filter-based tracking by taking the realistic capsule endoscope transition model into consideration.

A design scheme for a high-speed differential-input limiting transimpedance amplifier (TIA) was developed. The output-stage amplifier of the TIA is investigated in detail in order to suppress undershoot and ringing in the output waveform. The amplifier also includes a peak detector for the received signal strength indicator (RSSI) output, which is used to control the optical demodulator for differential-phase-shift-keying or differential-quadrature-phase-shift-keying formats. The limiting TIA was fabricated on the basis of 1-µm emitter-width InP-based heterojunction-bipolar-transistor (HBT) IC technology. Its differential gain is 39 dB, its 3-dB bandwidth is 27 GHz, and its estimated differential transimpedance gain is 73 dBΩ. The obtained output waveform shows that the developed design scheme is effective for suppressing undershoot and ringing.

This paper describes an innovative, high-speed optical backboard bus composed of an optical star coupler, optical-transmitter modules, optical-receiver modules, and optical multi-mode glass fibers. A highly efficient optical coupling structure with an aspherical lens and a laser diode was designed to achieve a coupling efficiency of 90%, enabling distribution of optical signals at up to 1 Gb/s to 50 function boards. Embedded optical fibers in a printed circuit board were used to achieve precise control of the optical propagation delay times and permit a high packaging density. We developed small laser-diode and photo-diode modules suitable for optical coupling with the embedded fibers. A fabricated prototype optical backboard bus controlled by a controller IC mounted on a function board was able to successfully distribute high-speed optical signals to function boards with a high packaging density.

We define the Reallocation Problem to determine whether we can move products from their current store-houses to target storehouses in a number of moves which is less than or equal to a given number. This problem is defined simply and can be applied to many practical problems. We give necessary and sufficient conditions for feasibility for Reallocation Problems under various conditions, and propose liner time algorithms, when the volume of the products is restricted to 1. Moreover, we show that the Reallocation Problem is NP-complete in the strong sense, when the volume of the products is not restricted.